#include "skynet.h"

#include "skynet_timer.h"
#include "skynet_mq.h"
#include "skynet_server.h"
#include "skynet_handle.h"
#include "spinlock.h"

#include <time.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

typedef void (*timer_execute_func)(void *ud,void *arg);

#define TIME_NEAR_SHIFT 8
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)
#define TIME_LEVEL_SHIFT 6
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)
#define TIME_NEAR_MASK (TIME_NEAR-1)
#define TIME_LEVEL_MASK (TIME_LEVEL-1)

struct timer_event {
	uint32_t handle; //service的句柄
	int session; //service消息队列的session, 通过它可以找到具体的事件函数
};

struct timer_node {
	struct timer_node *next;
	uint32_t expire; //该节点到期的滴答数
};

struct link_list {
	struct timer_node head;
	struct timer_node *tail;
};

struct timer {
	struct link_list near[TIME_NEAR]; //近期链表
	struct link_list t[4][TIME_LEVEL]; //散列链表
	struct spinlock lock;
	uint32_t time; //初始值为0, 单调递增, 每一个时钟滴答, 计数+1
	uint32_t starttime; //时间戳, 从时间原点开始计时, skynet启动时赋值, 后续不再改变(单位: 1s)
	uint64_t current; //时间段, starttime到目前, 绝对意义上已经过了多长时间(单位: 0.01s = 10ms)
	uint64_t current_point; //时间戳, 计时起点是操作系统开机, 终点是现在, 代表绝对的逝去时间, 不受用户改变操作系统时间的影响(单位: 0.01s = 10ms)
};

static struct timer * TI = NULL;

//清空link_list, 让它不包含任何定时器节点, 返回link_list头结点的next
static inline struct timer_node *
link_clear(struct link_list *list) {
	struct timer_node * ret = list->head.next;
	list->head.next = 0; //相当于 =null
	list->tail = &(list->head);

	return ret;
}

//将一个timer_node添加到link_list的尾部
static inline void
link(struct link_list *list,struct timer_node *node) {
	list->tail->next = node;
	list->tail = node;
	node->next=0;
}

static void
add_node(struct timer *T, struct timer_node *node) {
	uint32_t time = node->expire;
	uint32_t current_time = T->time;
	
	//TIME_NEAR_MASK = 255, 两个数二进制由低位起的前7位并不影响比较的结果, 但其他位要完全相同, 即必须在0~256个时钟滴答内到期的才放到near中
	if ((time|TIME_NEAR_MASK)==(current_time|TIME_NEAR_MASK)) {
		link(&T->near[time&TIME_NEAR_MASK], node); //time&TIME_NEAR_MASK, 通过位运算直接算出node该放到256个槽位中的哪个上
	} else { //确定node要放到哪个等级的轮上
		int i;
		uint32_t mask=TIME_NEAR << TIME_LEVEL_SHIFT;
		for (i=0;i<3;i++) {
			//这里的比较逻辑与上面的类似, 两个数二进制由低位起的前x位不影响比较结果
			if ((time|(mask-1))==(current_time|(mask-1))) {
				break;
			}
			mask <<= TIME_LEVEL_SHIFT;
		}

		//确定放到哪个槽位
		link(&T->t[i][((time>>(TIME_NEAR_SHIFT + i*TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK)], node);
	}
}

static void
timer_add(struct timer *T, void *arg, size_t sz, int time) {
	struct timer_node *node = (struct timer_node *)skynet_malloc(sizeof(*node)+sz);
	memcpy(node+1,arg,sz); //从arg复制sz个字节的数据到node+1指向的地址处

	SPIN_LOCK(T);

	node->expire=time+T->time;
	add_node(T,node);

	SPIN_UNLOCK(T);
}

static void
move_list(struct timer *T, int level, int idx) {
	struct timer_node *current = link_clear(&T->t[level][idx]);
	while (current) {
		struct timer_node *temp=current->next;
		add_node(T,current);
		current=temp;
	}
}

static void
timer_shift(struct timer *T) {
	int mask = TIME_NEAR;
	uint32_t ct = ++T->time; //无符号整型自增到溢出数值范围时会自动归零
	if (ct == 0) { //溢出时ct == 0特判，如果走else的分支会进入死循环
		move_list(T, 3, 0);
	} else {
		uint32_t time = ct >> TIME_NEAR_SHIFT; //time = ct缩小256倍
		int i = 0;

		//while()括号内的循环判断条件分析：
		//循环的第一遍，先以当前的时钟滴答数ct对256取模，如果等于0，说明near轮已经转完一圈，t[0]轮需要向前跳一个槽，并把槽内的定时节点分配到near轮上
		//循环的后几遍，以当前的时钟滴答数ct对256的某个倍数取模，如果等于0，说明对应的t[i-1]轮已经转完一圈，需要使t[i]轮向前跳一个槽，把槽内的定时节点分配到比它低级的各个轮上

		//循环的内部分析：
		//想象一下，我们有near、t[0]、t[1]、t[2]、t[3]一共五个轮，初始情况下每个轮的“针”都指向轮内的第一个槽，这轮内的第一个槽里，实质上是没有任何定时节点的；
		//near轮第一个槽里的定时节点已经被处理掉，t[0]轮第一个槽里的定时节点已经被分配到near轮上，t[1]轮第一个槽里的定时节点已经被分配到比它低级的轮上
		//所以，t[i]轮有64个槽位，编号是0~63，“针”由63号槽跳到0号槽时，触发一次 从下一个轮的某个槽中取定时节点分配到低级轮中 的机制

		// 当T->time的第1-8位不全为0时，不需要分配，因为此时near轮还没转完，还处于256周期内；
		// 当T->time的第1-8位全为0 且 T->time的第9-14位不全为0时，重新分配T[0]的某个槽位，每2^8个滴答数分配一次；
		// 当T->time的第1-14位全为0 且 T->time的第15-20位不全为0时，重新分配T[1]的某个槽位，每2^(8+6)个滴答数分配一次；
		// 当T->time的第1-20位全为0 且 T->time的第21-26位不全为0时，重新分配T[2]的某个槽位，每2^(8+6+6)个滴答数分配一次；
		// 当T->time的第1-26位全为0 且 T->time的第27-32位不全为0时，重新分配T[3]的某个槽位，每2^(8+6+6+6)个滴答数分配一次；
		while ((ct & (mask-1))==0) {
			int idx = time & TIME_LEVEL_MASK; //“针”指向的槽位
			if (idx!=0) {
				move_list(T, i, idx);
				break;
			}
			mask <<= TIME_LEVEL_SHIFT; //mask扩大64倍
			time >>= TIME_LEVEL_SHIFT; //time缩小64倍
			++i;
		}
	}
}

//对以current开头的定时节点链表进行遍历处理
static inline void
dispatch_list(struct timer_node *current) {
	do {
		//这个强转没太看懂, 后来研究了下timer_add那块的逻辑, 有一个timer_event结构被用memcpy将数据复制到了timer_node结构之后的地址上
		//于是一个timer_node对应一个timer_event的关系便被确定了下来, 这里是根据timer_node的地址重新取出timer_event的内容去使用
		struct timer_event * event = (struct timer_event *)(current+1); 
		struct skynet_message message;
		message.source = 0;
		message.session = event->session;
		message.data = NULL;
		message.sz = (size_t)PTYPE_RESPONSE << MESSAGE_TYPE_SHIFT;

		skynet_context_push(event->handle, &message); //向指定服务发送消息，指定服务接到后，lua vm中找到对应的挂起协程，执行func的内容
		
		//释放本次循环已处理的定时器节点的存储空间并遍历到下一个结点
		struct timer_node * temp = current;
		current=current->next;
		skynet_free(temp);
	} while (current);
}

static inline void
timer_execute(struct timer *T) {
	int idx = T->time & TIME_NEAR_MASK; //T->time与255进行按位与运算, 相当于以255为模进行取余操作
	
	while (T->near[idx].head.next) {
		struct timer_node *current = link_clear(&T->near[idx]);
		SPIN_UNLOCK(T);
		// dispatch_list don't need lock T
		dispatch_list(current);
		SPIN_LOCK(T);
	}
}

//对应TI-time每自增1执行1次
static void 
timer_update(struct timer *T) {
	SPIN_LOCK(T);

	// try to dispatch timeout 0 (rare condition)
	timer_execute(T);

	// shift time first, and then dispatch timer message
	timer_shift(T);

	// try to dispatch timeout 1
	timer_execute(T);

	SPIN_UNLOCK(T);
}

static struct timer *
timer_create_timer() {
	//申请空间然后置零
	struct timer *r=(struct timer *)skynet_malloc(sizeof(struct timer));
	memset(r, 0, sizeof(*r));

	int i,j;

	//清空近期链表
	for (i=0;i<TIME_NEAR;i++) {
		link_clear(&r->near[i]);
	}

	//清空散列链表
	for (i=0;i<4;i++) {
		for (j=0;j<TIME_LEVEL;j++) {
			link_clear(&r->t[i][j]);
		}
	}

	SPIN_INIT(r)

	r->current = 0;

	return r;
}

//供lua调用的增加定时器事件的函数
int
skynet_timeout(uint32_t handle, int time, int session) {
	if (time <= 0) {
		struct skynet_message message;
		message.source = 0;
		message.session = session;
		message.data = NULL;
		message.sz = (size_t)PTYPE_RESPONSE << MESSAGE_TYPE_SHIFT;

		if (skynet_context_push(handle, &message)) {
			return -1;
		}
	} else {
		struct timer_event event;
		event.handle = handle;
		event.session = session;
		timer_add(TI, &event, sizeof(event), time);
	}

	return session;
}

// centisecond: 1/100 second
static void
systime(uint32_t *sec, uint32_t *cs) {
	struct timespec ti;
	clock_gettime(CLOCK_REALTIME, &ti);
	*sec = (uint32_t)ti.tv_sec;
	*cs = (uint32_t)(ti.tv_nsec / 10000000);
}

//以操作系统启动为起点开始计时, 当前的时间戳
static uint64_t
gettime() {
	uint64_t t;
	struct timespec ti;
	clock_gettime(CLOCK_MONOTONIC, &ti);
	t = (uint64_t)ti.tv_sec * 100; //秒 * 100 = 单位0.01s
	t += ti.tv_nsec / 10000000; //单位由ns变为0.01s
	return t;
}

//skynet定时器模块的驱动函数, 每2.5ms执行一遍
void
skynet_updatetime(void) {
	uint64_t cp = gettime();
	if(cp < TI->current_point) {
		skynet_error(NULL, "time diff error: change from %lld to %lld", cp, TI->current_point);
		TI->current_point = cp;
	} else if (cp != TI->current_point) {
		uint32_t diff = (uint32_t)(cp - TI->current_point); //离上一次执行updatetime经过的时间间隔, 精度0.01s
		TI->current_point = cp;
		TI->current += diff;
		int i;
		for (i=0;i<diff;i++) {
			timer_update(TI);
		}
	}
}

//返回skynet启动时的系统时间戳(精度: 秒, 从时间原点开始计时)
uint32_t
skynet_starttime(void) {
	return TI->starttime;
}

//返回时间段, starttime到现在经过了多长时间(精度: 0.01s = 10ms)
uint64_t 
skynet_now(void) {
	return TI->current;
}

void 
skynet_timer_init(void) {
	TI = timer_create_timer();
	uint32_t current = 0;
	systime(&TI->starttime, &current);
	TI->current = current;
	TI->current_point = gettime();
}

// for profile

#define NANOSEC 1000000000
#define MICROSEC 1000000

// 时间原点到当前的时间戳(单位:us)
uint64_t
skynet_thread_time(void) {
	struct timespec ti;
	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ti);

	return (uint64_t)ti.tv_sec * MICROSEC + (uint64_t)ti.tv_nsec / (NANOSEC / MICROSEC);
}
